// https://leetcode.cn/problems/longest-increasing-subsequence/

// 算法思路总结：
// 1. 使用贪心+二分查找求解最长递增子序列
// 2. 维护一个递增序列，表示当前最小末元素的LIS
// 3. 新元素大于序列末尾时直接扩展，否则替换第一个≥它的元素
// 4. 最终序列长度即为LIS长度（序列内容不一定真实）
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int m = nums.size();
        vector<int> subV;

        for (int i = 0 ; i < m ; i++)
        {
            if (subV.empty() || nums[i] > subV.back())
                subV.push_back(nums[i]);
            else
            {
                auto it = lower_bound(subV.begin(), subV.end(), nums[i]);
                *it = nums[i];
            }
        }

        return subV.size();
    }
};

int main()
{
    vector<int> v1 = {10,9,2,5,3,7,101,18}, v2 = {0,1,0,3,2,3};
    Solution sol;

    cout << sol.lengthOfLIS(v1) << endl;
    cout << sol.lengthOfLIS(v2) << endl;

    return 0;
}